COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	⊂2.	Introduction to the Winged Edge.⊃
C00007 00003	{H7O0,630,700
C00009 00004	
C00013 00005
C00017 00006	{QP6}⊂3.	Sequential Accessing.⊃
C00020 00007	⊂4.	Perimeter Accessing.⊃
C00028 00008	⊂5.	Basic Polyhedron Synthesis.⊃
C00031 00009		<Node Makers and Killers>. The MKNODE and  KLNODE are the raw
C00033 00010		<Wing Mungers>.   The  WING(edge1,edge2) routine finds  which
C00036 00011		<Part Tree Routines>. As mentioned before,  body nodes can be
C00038 00012	⊂6.	Edge and Face Splitting.⊃
C00041 00013	{O0,0,450L0,255FCJC} FIGURE 3 - ESPLIT AND KLEV.{
C00046 00014	{O0,630,450L0,255FCJC} FIGURE 4 - MKFE AND KLFE.{
C00051 00015	7. Conclusion.
C00052 ENDMK
C⊗;
⊂2.	Introduction to the Winged Edge.⊃

	The Winged Edge polyhedron representation is implemented as a
data structure composed  of small blocks of words containing pointers
and  data in  the  fashion  usual  to  graphics  and  simulation.  An
introduction to  such data structures  can be  found in Chapter  2 of
Knuth's  Art of Computer Programming [Knuth 1968].  Quickly  reviewing
Knuth's terminology,  a  node  is a  group  of consecutive  words  of
memory,  a field  is a  named portion  of a  node and  a link  is the
machine address of a node.  The notation for referring to a field  of
a  node  consists  simply  of the  field  name  followed  by  a  link
expression enclosed in  parentheses. For example, the two faces of an
edge node  whose link is  stored in  the variable  named "edge",  are
found in  the fields named  NFACE and PFACE,  and are referred  to as
NFACE(edge)   and  PFACE(edge).    Although  my  latest  language  of
implementation is PDP-10  machine code, examples  will be given in  a
fictional  programming  language which  combines  ALGOL with  Knuth's
node/link notation. 


{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;

L-30,-10;FB	}edge
{L-380,-10;	}NFACE(edge)
{L240,-10;	}PFACE(edge)
{L-70,-370;	}NVT(edge)
{L-70,350;	}PVT(edge)
{L-360,320;	}NCCW(edge)
{L-390,-360;	}NCW(edge)
{L220,320;	}PCW(edge)
{L260,-360;	}PCCW(edge)

{I1300,0;O0,630,950;
λ10;JC;FA}  ⊂FIGURE 1 - Winged Edge Topology.⊃

The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
	NFACE(edge)	Negative Face of edge.
	PFACE(edge)	Positive Face of edge.
	PVT(edge)		Positive Vertex of edge.
	NVT(edge)		Negative Vertex of edge.
	NCW(edge)		edge in Negative face Clockwise from edge.
	PCW(edge)		edge in Positive face Clockwise from edge.
	NCCW(edge)		edge in Negative face Counter Clockwise from edge.
	PCCW(edge)		edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}

	A polyhedron  in  made up  of four  kinds  of nodes:  bodies,
faces, edges and  vertices. The body node is the head of three rings:
a ring of  faces, a ring  of edges and  a ring  of vertices. In  this
context, a  ring is a doubly  linked circular list with  a head node.
Each face and each vertex points directly at only one of the edges on
its  perimeter. Each  edge  points  at  its two  faces  and  its  two
vertices. Completing the topology,  each edge node contains a link to
each of its  four immediate neighboring  edges clockwise and  counter
clockwise about its face perimeters as seen from the exterior side of
the surface of the polyhedron. These last four links are the wings of
the edge, which  provide the basis for  efficient face perimeter  and
vertex perimeter  accessing.  Finally,   the links of the  edge nodes
can  be  consistently oriented  with respect  to  the surface  of the
polyhedron so that the surface  always has two sides: the  inside and
the outside.
{|;λ10;JA}
BOX 1     {JC} WINGED EDGE STRUCTURES AND LINK NAMES.

	   ~Data Structures~				~Link Names~
	1. Face Ring of a Body.			NFACE	PFACE
	2. Edge Ring of a Body.			NED		PED
	3. Vertex Ring of a Body.			NVT		PVT
	4. First Edge of a Vertex.					PED
	5. First Edge of a Face.					PED
	6. The two faces of an edge:		NFACE	PFACE
	7. The two vertices of an edge:		NVT		PVT
	8. The four wing edges of an edge:	NCW  PCW  NCCW  PCCW
{|;λ30;JU}
	Observe that  there are twenty-two  link fields in  the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such  as PED
to serve different  roles depending on whether it applies  to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising  the structures are listed in  Box 1. The
ten link names include: NFACE and PFACE for two fields that  contain
face links in  edges and the  face ring, NED  and PED for  two fields
that  contain edge links,   NVT and  PVT for two  fields that contain
vertex links, and NCW,  PCW, NCCW and PCCW  for the four fields  that
contain edge links and are called the wings.

	By constraining the arrangement of links in an edge node both
the  surface  orientation   (interior  and  exterior)  and  a  linear
orientation of the edge as a directed vector can be encoded.   Figure
1 diagrams the arrangement of  the links comprising the topology of
an  edge of  a polyhedron  as viewed  from the  exterior side  of its
surface. Although  the vertices  in Figure  1 are  shown with  only
three  edges,   vertices  may have  any  number of  edges; the  other
potential edges would not  be directly linked to  the middle edge  of
the figure and so were not shown.

	To complete the representation, space is allocated to contain
the 3-D coordinates of each vertex in fields named XWC,  YWC and ZWC;
the initials  "WC" stand  for <World  Coordinates>. For  the sake  of
vision and display,  three more  words are allocated to hold
the  <Perspective  Projected coordinates>  of  each vertex  in fields
named XPP,  YPP  and ZPP.  Also a  word of thirty six status  bits is
carried in every node:  permanent status bits specify the type (body,
face, edge,  vertex,   etc.) of every  node,  temporary bits  provide
space for  operations such  as hidden  line elimination that  require
marking. Passing  now from necessities to  conveniences,  faces carry
exterior pointing  normal vectors  and several  words of  photometric
surface characteristics.   The face vectors are  derived from surface
topology  and vertex loci,  and so  they are not basic geometric data
as in some  representations. Bodies  carry a print  name, as well  as
four link fields (DAD,  SON, BRO,  SIS) for implementing a parts tree
data structure; and two link fields (CW  and CCW) for a body ring  of
all the bodies in the world model. Node  formats are given in Box 2
for an implementation based on fixed sized (twelve word) nodes.

	The  Winged Edge Polyhedron Representation  as just presented
is complete.  Edge  nodes carry most of  the topology,  vertex  nodes
carry the geometry,   face nodes carry the photometry  and body nodes
carry  the nomenclature and parts  tree structure.  The
point that  remains  to be  demonstrated,   is  that the  appropriate
subroutines   for  creating,     maintaining   and   exploiting  edge
orientation execute  efficiently  and  provide  good  primitives  for
solving  such  geometric  problems as  hidden  line  elimination  and
polyhedral intersection.

{Q;P6;}⊂3.	Sequential Accessing.⊃

	An immediate consequence of the ring structures is that the
faces, edges and vertices of a body are sequentially accessible in the
manner illustrated by the following lines of code:
{JA;W0;λ7;F3}
COMMENT APPLY A FUNCTION TO ALL THE FACES, EDGES AND VERTICES OF A BODY;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
	INTEGER F,E,V;
	F ← B; WHILE B≠(F←PFACE(F)) DO FN(F);	COMMENT APPLY FUNCTION TO FACES OF A BODY;
	E ← B; WHILE B≠(E←PED(E)) DO FN(E);	COMMENT APPLY FUNCTION TO EDGES OF A BODY;
	V ← B; WHILE B≠(V←PVT(V)) DO FN(V);	COMMENT APPLY FUNCTION TO VERTICES OF A BODY;
END;
{JUFA;W0;λ30;}
\The rings could of course have been traversed in the other direction by
invoking NVT, NED and NFACE in place of PVT, PED and PFACE. The reason
for doubly linked lists (i.e. rings) is rapid deletion. Finally, observe
that the face and vertex rings could be eliminated at the cost of having
a more complicated face/vertex sequential accessing method requiring a
visitation marking bit in the status word of face and vertex nodes.
⊂4.	Perimeter Accessing.⊃

	The perimeter  of  a face  is an  ordered list  of edges  and
vertices, the  perimeter of a vertex is an  ordered list of edges and
faces, and the perimeter of an edge is an ordered list  consisting of
exactly two  faces and two  vertices.  The perimeter  definitions are
caricatured   in  Figure  2.    One   virtue  of  the  winged  edge
representation  is  that both  vertex  and  face  perimeters  can  be
traversed in  either direction (clockwise or  counter clockwise) while
being dynamically maintained in "<one ring>".

{O0,630,350;L0,0;H3;FD
L0,-137;C6;L0,-137,0,170;C6;
L-44,10;FD}EDGE{
L-125,-170;FA}An Edge is surrounded{
L-120,-200;FA}by Faces and Vertices{
L0,200;JC;FC} FIGURE 2 - Three Kinds of Perimeters.{
L420,170,420-161,52;C6;
L420-161,52,420-100,-137;C6;
L420-100,-137,420+100,-137;C6;
L420+100,-137,420+161,52;C6;
L420+161,52,420,170;C6;
L420-45,-10;FD}FACE{
L420-125,-170;FA}A Face is surrounded{
L420-130,-200;FA}by Edges and Vertices{
L-420,0,-420-161,52;
L-420,0,-420-100,-137;
L-420,0,-420+100,-137;
L-420,0,-420+161,52;
L-420,170,-420,0;C6;
L-420-70,30;FD}VERTEX{
L-420-125,-170;FA}A Vertex is surrounded{
L-420-115,-200;FA}by Edges and Faces{O0,630,950;I590,0;JUFA}
	Given one  edge of a  face (or vertex)  perimeter,   the next
edge clockwise  (or counter clockwise) from the  given edge about the
particular face (or vertex) can be retrieved from the  data structure
with the assistance of two subroutines  called ECW and ECCW. The idea
of the  edge clocking routines is to match the given face (or vertex)
with one of  the faces (or  vertices) of the  given edge and to  then
return the appropriate wing. A  possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
	IF PFACE(E)=FV THEN RETURN(PCCW(E));
	IF NFACE(E)=FV THEN RETURN(NCCW(E));
	IF PVT(E)=FV   THEN RETURN(PCW(E));
	IF NVT(E)=FV   THEN RETURN(NCW(E));
	FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
	IF PFACE(E)=FV THEN RETURN(PCW(E));
	IF NFACE(E)=FV THEN RETURN(NCW(E));
	IF PVT(E)=FV   THEN RETURN(NCCW(E));
	IF NVT(E)=FV   THEN RETURN(PCCW(E));
	FATAL;
END "ECW";
{W0;JUFA;λ30;}
\The first edge  of a face  or vertex is (of  course) immediately
available from the  PED field of the face or vertex. For example, the
two procedures below can be used to visit all the edges of a face or
all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
PROCEDURE APPLY (PROCEDURE FN; INTEGER F);
BEGIN
	INTEGER E,E0;
	E←E0←PED(F);
	DO FN(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
PROCEDURE APPLY (PROCEDURE FN; INTEGER V);
BEGIN
	INTEGER E,E0;
	E←E0←PED(V);
	DO FN(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
	Using the same idea as in the  edge clocking routines, a face
or vertex can be  retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or  counter clockwise from a  given edge with respect  to a
given  vertex;  VCW and  VCCW  which  return the  vertex  clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which returns the face  or vertex of the given edge opposite the
given face or vertex.  Together the seven routines: ECW, ECCW,   VCW,
VCCW, FCW,  FCCW  and OTHER exhaust the possible  oriented retrievals
from  an edge node; they  also alleviate the need  to ever explicitly
reference a wing  field when traveling the  surface of a  polyhedron.
With  node type  checking the primitives can be made stronger, for example
ECCW(vertex,face) is implemented to return the edge counter clockwise
from the given vertex about the given face.
With  node type  checking and  signed arguments  the seven  perimeter
accessing  routines could  even be  replaced by  a single  routine perhaps
named PERIMETER_FETCH or PGET. On the other hand, I  favor having the
proliferation  of accessing  names for the sake  of  documenting the
clocking direction and the types of nodes involved.

	Two remaining accessing routines, of minor importance,
are BGET(entity)  and LINKED(entity,entity). BGET of  a face, edge or
vertex merely cycles the appropriate ring to retrieve the body of the
given  entity.    The  LINKED  routine  determines  whether  its  two
arguments  (faces,   edges or vertices)  are adjacent;  there are six
LINKED cases:  (i) Face-Face, returns  a common  edge or FALSE;  (ii)
Face-Edge,  returns  boolean  value  F=PFACE(E) ∨  F=NFACE(E);  (iii)
Edge-Edge,  returns  a  common  vertex  or  false;  (v)  Edge-Vertex,
returns  boolean  value  V=PVT(E)  ∨  V=NVT(E);  (vi)  Vertex-Vertex,
returns common edge or FALSE. (As in LISP, zero is false and non-zero
is true).

⊂5.	Basic Polyhedron Synthesis.⊃
{|;λ10;JA}
BOX 3 {JC} LOWEST LEVEL WINGED EDGE ROUTINES.

	<Node Makers:>		MKNODE, MKB, MKF, MKE, MKV, MKTRAM.
	<Node Killers:>		KLNODE, KLB, KLF, KLE, KLV.
	<Wing Mungers:>		WING, INVERT, EVERT.
	<Surface Fetchers:>		ECW, ECCW, OTHER, VCW, VCCW, FCW, FCCW, LINKED.
	<Parts Tree Routines:>	BDET, BATT, BGET.
{|;λ30;JU}
	There  are  sixteen  routines  for  node  creation  and  link
manipulation which when  combined with the nine accessing routines of
the previous  section  form  the  nucleus of  a  polyhedron  modeling
system.    These routines  are  very  low  level  in that  the  final
applications  user of winged polyhedra will  never explicitly need to
make a node  or mung a  link. The word  <mung> (meaning to modify  an
existing  structure by altering  links in  place) is LISP  slang that
deserves to be promoted into  the technical jargon; traditionally,  a
mung routine is one  which makes applications of the  LISP primitives
RPLACA and RPLACD.   The twenty five routines listed in Box 3 are the
bedrock for  the  Euler  primitives,  which are  an  elegant  set  of
subroutines for altering polyhedra while always maintaining the Euler
relation:  F-E+V=2*B-2*H between the numbers of bodies, faces, edges,
vertices and  handles.   Examples  of Euler  primitives are  given in
another paper written for this conference [Eastman, Lividini & Stoker
1975] as well as Section 3 of [Baumgart 1974B]; and so will not  need
to be further discussed. 
	<Node Makers and Killers>. The MKNODE and  KLNODE are the raw
storage  allocation routines which  fetch or  return a node  from the
available free  storage. The  MKB routine  creates a  body node  with
empty face, edge  and vertex rings; the body is  placed into the body
ring of the world model.  The MKF, MKE and MKV each take one argument
and create a new face, edge  or vertex node in the ring of  the given
entity;   with  type  checking   these  three  primitives   could  be
consolidated.  Finally the MKTRAM  node creates a <tram node>,  which
consists of  twelve real  numbers that  represent either a  Euclidean
transformation  or a  Cartesian frame of  reference depending  on the
context.  As  a  cartesian  frame  of  reference  the  tram  node  is
interpreted as a  3-D locus in world coordinates with  a right handed
triad  of orthogonal unit vectors; as  a Euclidean transformation the
tram node  is  interpreted  as a  translation  vector followed  by  a
rotation  matrix.  Tram  nodes  are  further explained  in  [Baumgart
1974B].  The corresponding kill routines KLB, KLF, KLE and KLV remove
the entity  from  its respective  ring and  return its  node to  free
storage. 

	<Wing Mungers>.   The  WING(edge1,edge2) routine finds  which
face  and vertex  the arguments  edge1 and edge2  have in  common and
stores the  wing pointers between  edge1 and  edge2 accordingly;  the
exact link manipulations  are illustrated in the  example coding of
the  WING procedure  immediately following  this paragraph. Recalling
that edges  are directed vectors,   the  INVERT(E) routine flips  the
direction  of an  edge by  swapping the  contents of  the appropriate
fields as follows:  PFACE(E)↔NFACE(E); PVT(E)↔NVT(E);  NCW(E)↔NCCW(E)
and PCW(E)↔PCCW(E).  Finally,  the EVERT(B) routine
turns  a  body  inside  out,   by
performing the following link swaps on all the edges of the  given body:
PFACE(E)↔NFACE(E); NCW(E)↔PCCW(E); and NCCW(E)↔PCW(E).
{JA;λ7;F3;W120,1260,0,1900;}
PROCEDURE WING(INTEGER  E1,E2);
BEGIN
	IF PVT(E1)=PVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN  PCW(E1)←E2;NCCW(E2)←E1;END;
	IF PVT(E1)=PVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCCW(E1)←E2; PCW(E2)←E1;END;
	IF PVT(E1)=NVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN  PCW(E1)←E2;PCCW(E2)←E1;END;
	IF PVT(E1)=NVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCCW(E1)←E2; NCW(E2)←E1;END;
	IF NVT(E1)=PVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCCW(E1)←E2; PCW(E2)←E1;END;
	IF NVT(E1)=PVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN  NCW(E1)←E2;NCCW(E2)←E1;END;
	IF NVT(E1)=NVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCCW(E1)←E2; NCW(E2)←E1;END;
	IF NVT(E1)=NVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN  NCW(E1)←E2;PCCW(E2)←E1;END;
END;{λ30;W0,1260,150,1800;JUFA}
	<Part Tree Routines>. As mentioned before,  body nodes can be
grouped into a  tree structure of parts. The parts tree consumes four
link positions (DAD,   SON,   BRO,   SIS) and is  maintained in  body
nodes by  the following  primitives: BDET(body)  detachs a  body node
from the  parts tree,  BATT(body1,body2) attachs body1 to the ring of
children belonging to body2,  and BGET(entity) returns  the body node
at the head of the given face, edge or vertex ring. The SON field of a
body may contain a pointer to a headless ring of subpart bodies,  the
ring of subparts is maintained in the  BRO (brother) and SIS (sister)
fields, and  each subpart contains a  pointer back to its parent
in its DAD field. At present, the notion of a body is coincident with
the notion  of a  connected polyhedron;  however by  allowing several
bodies to  be associated with a single polyhedral surface, a flexible
object such as an animal could be represented.

⊂6.	Edge and Face Splitting.⊃

	The most important property  of  the winged  edge
representation is that edges and faces can be split using subroutines
that make  only local  alterations  to the  data structure;  and  the
splits can  easily be  removed (since the  doubly linked  rings allow
rapid deletion of nodes from a body). The edge split routine, ESPLIT,
makes a new edge  and a new vertex  and places them into  the surface
topology as shown in  Figure 3; the kill edge-vertex routine, KLEV,
undoes an ESPLIT.  The face split routine,  MKFE, creates a new  edge
and a new face and places them into the  surface topology as shown in
Figure 4; the kill face-edge routine, KLFE,  undoes a MKFE.

	The rest  of this section concerns  implementation;
the use of the split and  kill
routines illustrate a  pattern which  applies to the  coding of any
operations on winged edge structures.  In a typical situation,
there are five steps: first,  get the proper kinds of nodes  into the
body rings using the MKF,  MKE,  MKV primitives; second, position the
vertices by setting their XWC,  YWC, ZWC fields; third, connect  each
vertex  and face  to one  of  its edges  by  setting face/vertex  PED
fields;  fourth,   connect each  edge to  its two  faces and  its two
vertices by setting the NFACE, PFACE,  NVT,  PVT fields of  the edge;
finally,  set up  the wing  perimeter pointers  by applying  the WING
primitive to the pairs of edges to be mated.{Q}
{O0,0,450;L0,255;FCJC} FIGURE 3 - ESPLIT AND KLEV.{
O0,630-300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;   L0,0,0,122;I∂2,∂2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166;  L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;

L-200,-240;}BEFORE: VNEW ← ESPLIT(EDGE);{
L-200,-270;}AFTER:   EDGE ← KLEV(VNEW);{

O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;   L0,0,0,122;I∂2,∂2;C6;L2,2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}VNEW{
L15,50;FA}ENEW{
L15,-75;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166;  L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE:  EDGE ← KLEV(VNEW);{
L-200,-240;}AFTER:  VNEW ← ESPLIT(EDGE);{
O0,630,950;
JA;I800,0;↓;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER EDGE);
BEGIN "ESPLIT"
	INTEGER VNEW,ENEW;
COMMENT CREATE A NEW EDGE AND VERTEX;
	VNEW ← MKV(PVT(EDGE));
	ENEW ← MKE(EDGE);
COMMENT CONNECT VERTICES & FACES TO EDGES;
	PVT(ENEW) ← PVT(EDGE);
	NVT(ENEW) ← VNEW;
	PVT(EDGE) ← VNEW;
	PFACE(ENEW) ← PFACE(EDGE);
	NFACE(ENEW) ← NFACE(EDGE);
COMMENT CONNECT EDGES TO VERTICES;
	IF PED(PVT(EDGE)=EDGE THEN
	  PED(PVT(EDGE))←ENEW;
	PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
	NCW(ENEW) ← EDGE; PCCW(ENEW) ← EDGE;
	PCW(EDGE) ← ENEW; PCCW(EDGE) ← ENEW;
	WING(NCCW(EDGE),ENEW);
	WING(PCW(EDGE),ENEW);
	RETURN(VNEW);
END "ESPLIT";
{JA;↑;W620;λ10;F3}
INTEGER PROCEDURE KLEV (INTEGER VNEW);
BEGIN "KLEV"
	INTEGER EDGE,ENEW,V,F,B;
	ENEW ← PED(VNEW);
	EDGE ← ECCW(ENEW,VNEW);
COMMENT ORIENT EDGES AS IN DIAGRAM;
	IF NVT(ENEW) ≠ VNEW THEN INVERT(ENEW);
	IF PVT(EDGE) ≠ VNEW THEN INVERT(EDGE);
COMMENT TIE E TO ITS NEW UPPER VERTEX AND WINGS;
	V ← PVT(EDGE) ← PVT(ENEW);
	WING(PCW(ENEW),EDGE);
	WING(NCCW(ENEW),EDGE);
COMMENT ELIMINATE OCCURRENCES OF ENEW IN F AND V;
	IF PED(V)=ENEW THEN PED(V) ← EDGE
	IF PED(PFACE(EDGE))=ENEW THEN
	  PED(PFACE(EDGE))←EDGE;
	IF PED(NFACE(EDGE))=ENEW THEN
	  PED(NFACE(EDGE))←EDGE;
COMMENT REMOVE NODES FROM RINGS AND RETURN EDGE;
	KLV(VNEW);
	KLE(ENEW);
	RETURN(EDGE);
END "KLEV";
{W0,1260;λ30;JUFA}
	The actual routines differ slightly from those given above in
that  they do  argument type  checking  and data  structure checking;
nevertheless, a diagnostic trace of the implemented  version reveals
that the ESPLIT routine executes an average of 170 PDP-10 instructions
and the KLEV routine executes an average of 200 instructions.
{O0,630,450;L0,255;FCJC} FIGURE 4 - MKFE AND KLFE.{
O0,630-300,450;H4;L2,-120;C6;L2,124;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-7;FA}FACE{
L-172,166,0,122,172,166;  L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;

L-200,-240;}BEFORE: ENEW ← MKFE(V1,FACE,V2);{
L-200,-270;}AFTER:   FACE ← KLFE(ENEW);{

O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;L0,0,0,122;I∂2,∂2;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-190;FA}NVT{
L-20,170;FA}PVT{
L15,-7;FA}ENEW{
L-200,15;}NFACE{
L-200,-25;}FNEW{
L140,15;}PFACE{
L140,-25;}FACE{
L-172,166,0,122,172,166;  L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE:  FACE ← KLFE(ENEW);{
L-200,-240;}AFTER:  ENEW ← MKFE(V1,FACE,V2);{
O0,630,950;JA;λ10;I800,0;↓;F3}
INTEGER PROCEDURE MKFE(INTEGER V1,FACE,V2);
BEGIN "MKFE"
	INTEGER V1,V2,FNEW,ENEW,E,E0,B,V;
COMMENT CREATE NEW FACE & EDGE;
	FNEW ← MKF(FACE); ENEW ← MKE(PED(FACE));
COMMENT LINK NEW EDGES TO ITS FACES & VERTICES;
	PED(F) ← PED(FNEW) ← ENEW;
	PFACE(ENEW) ← F; NFACE(ENEW) ← FNEW;
	PVT(ENEW) ← V1; NVT(ENEW) ← V2;
COMMENT GET THE WINGS OF THE NEW EDGE;
	E2 ← PED(V1);
	DO E2←ECW((E1←E2),V1) UNTIL FCW(E1,V1)=FACE;
	E4 ← PED(V1);
	DO E4←ECW((E3←E4),V2) UNTIL FCW(E3,V2)=FACE;
COMMENT SCAN CCW FROM V1 REPLACING F'S WITH FNEW;
	E ← E2;
	DO IF PFACE(E)=FACE THEN PFACE(E)←FNEW
	 ELSE NFACE(E)←FNEW;
	UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK THE WINGS;
	WING(E1,ENEW); WING(E2,ENEW);
	WING(E3,ENEW); WING(E4,ENEW);
	RETURN(ENEW);
END;
{JA;↑;W635;λ10;F3}
INTEGER PROCEDURE KLFE (INTEGER ENEW);
BEGIN "KLFE"
	INTEGER FNEW,FACE,V1,V2,E,E1,E2,E3,E4;
COMMENT PICKUP ALL THE LINKS OF ENEW;
	FACE ← PFACE(ENEW); FNEW ← NFACE(ENEW);
	V1 ← PVT(ENEW);  V2 ← NVT(ENEW);
	E1 ← PCW(ENEW);	E2 ← NCCW(ENEW);
	E3 ← NCW(ENEW);	E4 ← PCCW(ENEW);
COMMENT GET ENEW LINKS OUT OF FACE, V1 AND V2;
	IF PED(V1) = ENEW THEN PED(V1) ← E1;
	IF PED(V2) = ENEW THEN PED(V2) ← E3;
	IF PED(FACE)=ENEW THEN PED(FACE)←E3;
COMMENT GET RID OF FNEW APPEARANCES;
	E ← E2;
	DO IF PFACE(E)=FNEW THEN PFACE(E)←FACE
	 ELSE NFACE(E)←FACE;
	UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK WINGS TOGETHER ABOUT FACE;
	WING(E2,E1);WING(E4,E3);
	KLF(FNEW);KLE(ENEW);
	RETURN(FACE);
END;
{W0,1260,0,1900;λ30;JUFA}

	Again, the actual routines differ from those given above in that 
they do argument type checking and data structure checking. The above two routines
typically take about twice as long to execute as the previous pair; notice
that the execution time is dependent on the length of face perimeters,
which are mostly three or four edges long.{W0,1260,0,1900;
7. Conclusion.

	The narrow technical point of this paper is that a polyhedral
representation  with  a  coherent  easy  to  change topology  can  be
constructed.  The larger philosophical point is  that computer vision
perhaps can be realized by using computer graphics techniques to keep
an  internal  mental simulation  in  sync  with the  of  the external
physical reality.